/*
 * @Author: lei
 * @Description: 计数排序
 * @FilePath: /new/countingsort.cc
 */

#include <iostream>

#include "sort.h"
using namespace std;
// g++ -o countingsort countingsort.cc -std=c++11 -g
void CountingSort(vector<int>& v) {
  int len = v.size();
  if (!len) return;
  int max = 0;
  // 计算v中元素的最大跨度
  for (auto& t : v) {
    if (t > max) max = t;
  }
  // 计数
  vector<int> count(max + 1, 0);
  for (auto& t : v) {
    count[t]++;
  }
  // 累计，计算最终下标
  for (int i = 1; i < max + 1; i++) {
    count[i] += count[i - 1];
  }
  // 存放排序结果
  vector<int> output(len, 0);
  for (auto& t : v) {
    output[count[t] - 1] = t;
    count[t]--;
  }
  v = output;
}

// int main() {
//   vector<int> v{1, 8, 3, 89, 0, 34, 90, 89, 92, 6};
//   for (auto& t : v) cout << t << " ";
//   cout << endl;
//   CountingSort(v);
//   for (auto& t : v) cout << t << " ";
//   cout << endl;
//   return 0;
// }

// 计数排序的时间复杂度为O(N+K),k表示数据的范围大小。
// 空间主要是长度为 k 的计数数组和长度为 n 的结果数组，空间复杂度也是O(N+K)
// 计数排序只适用于数据范围不大的场景
// TODO:考虑unordered_map 和 排序负数、排序小数？